package com.study.suanfa.paixu;

import java.util.Arrays;

/**
 * @description: kuaisu  快速排序
 * @date: 2020/12/2 15:48
 * @author: hcm
 * @version: 1.0
 */
public class kuaisu {

    public static void main(String[] args) {
        int[] arr = {4,3,5,2};
        int left=0,right=0;
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }



    /**
     * 快速排序
     */
    private static void quickSort(int[] arr, int left, int right) {
        //左下标
        int l = left;
        //右下标
        int r = right;
        //中轴
        int mid = arr[(left+right)/2];
        //交换变量
        int temp = 0;
        //循环让比中点值小的全部放左边
        while (l<r){
            //左边一直找大于中点的值
            while (arr[l]<mid){
                l+=1;
            }
            //右边一直找小于中点的值
            while (arr[r]>mid){
                r-=1;
            }

            //如果左边大于等于右边，左边全部小于中点，右边全部大于中
            if(l>=r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完发现arr[l] == mid,向前一步
            if(arr[l] == mid){
                r -= 1;
            }
            //arr[r] == mid
            if(arr[r] == mid){
               l+=1;
            }
        }
        if(l == r){
            l+=1;
            r-=1;
        }

        //想左递归
        if(left<r){
            quickSort(arr,left,r);
        }

        //右递归
        if(right>l){
            quickSort(arr,l,right);
        }
    }
}
